package 力扣;
//   给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
public class 旋转链表 {
    public static void main(String[] args) {

    }
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
  //1➡2➡3➡4➡5  k=2
  //可以看做3➡4之间断开，分成两段，4➡️5段（由k个结点组成的段）重新链接至1➡️2➡️3前
  //使用快慢指针找到最后k个结点，重新和前段相连接即为旋转后的链表。
  //需要注意的是快慢指针区间一共包含k+1个结点，即left结点为3，right结点为5，因为需要修改
  //newhead = left.next，left.next = null right.next = head
    public static ListNode rotateRight(ListNode head, int k) {
         if (head==null)
             return head;
         ListNode p=head;
         int len=1;
         //计算链表的长度
        while (p.next!=null){
            p=p.next;
            len++;
        }
        int num=k%len;
        if (num==0)
            return head;
        //设置左右指针
        ListNode left=head;
        ListNode right=head;
        for (int i = 0; i < num; i++) {
            right=right.next;
        }
        while (right.next!=null){
            right=right.next;
            left=left.next;
        }
        //新的头节点
        ListNode newHead=left.next;
        left.next=null;
        right.next=head;
        return newHead;
    }
}
